#include "ResidueField.h"
#include "NumberTheory.h"


ResidueField::ResidueField(const Integer &n, const Integer &p, bool ok)
{
	if (!ok && !NumberTheory::IsPrime(p))
		throw;

	this->num = n % p;
	this->mod = p;
}

std::string ResidueField::str() const
{
	return this->num.str();
}

std::ostream& operator<<(std::ostream &out, const ResidueField &n)
{
	return out << n.str();;
}

bool IsSameSystem(const ResidueField &m, const ResidueField &n)
{
	return m.mod == 0 || n.mod == 0 || m.mod == n.mod;
}

bool operator==(const ResidueField &lhs, const ResidueField &rhs)
{
	if (lhs.mod == 0 && rhs.mod == 0)
		return lhs.num == rhs.num;
	else if (lhs.mod == 0)
		return lhs.num % rhs.mod == rhs.num;
	else if (rhs.mod == 0)
		return rhs.num % lhs.mod == lhs.num;
	else
		return lhs.mod == rhs.mod && lhs.num == rhs.num;
}

bool operator!=(const ResidueField &lhs, const ResidueField &rhs)
{
	return !(lhs == rhs);
}

bool operator<(const ResidueField &lhs, const ResidueField &rhs)
{
	if (!IsSameSystem(lhs, rhs))
		throw;

	if (!((lhs.mod == 0) ^ (rhs.mod == 0)))
		return lhs.num < rhs.num;
	else if (lhs.mod == 0)
		return lhs.num % rhs.mod < rhs.num;
	else
		return rhs.num % lhs.mod > lhs.num;
}

bool operator<=(const ResidueField &lhs, const ResidueField &rhs)
{
	return !(rhs > lhs);
}

bool operator>(const ResidueField &lhs, const ResidueField &rhs)
{
	return rhs < lhs;
}

bool operator>=(const ResidueField &lhs, const ResidueField &rhs)
{
	return !(lhs < rhs);
}

ResidueField ResidueField::operator-() const
{
	if (this->mod == 0)
		return ResidueField(-this->num);
	else
		return ResidueField(this->mod - this->num, this->mod, true);
}

ResidueField Inverse(const ResidueField &n)
{
	if (n.mod == 0)
		throw;

	if (n.num == 0)
		throw;

	Integer a, b;
	NumberTheory::ExGCD(n.num, n.mod, a, b);
	return ResidueField(std::sgn(a) == 1 ? a : n.mod + a, n.mod, true);
}

ResidueField operator+(const ResidueField &lhs, const ResidueField &rhs)
{
	if (!IsSameSystem(lhs, rhs))
		throw;

	if (lhs.mod == 0)
	{
		if (rhs.mod == 0)
			return ResidueField(lhs.num + rhs.num);
		else
			return ResidueField((lhs.num + rhs.num) % rhs.mod, rhs.mod, true);
	}
	else
		return ResidueField((lhs.num + rhs.num) % lhs.mod, lhs.mod, true);
}

ResidueField& ResidueField::operator+=(const ResidueField &addend)
{
	if (!IsSameSystem(*this, addend))
		throw;

	if (this->mod == 0)
	{
		if (addend.mod == 0)
		{
			this->num += addend.num;
			return *this;
		}
		else
			return *this = ResidueField((this->num + addend.num) % addend.mod, addend.mod, true);
	}
	else
	{
		this->num = (this->num + addend.num) % this->mod;
		return *this;
	}
}

ResidueField& ResidueField::operator++()
{
	return *this += 1;
}

ResidueField ResidueField::operator++(int)
{
	ResidueField n(*this);
	*this += 1;
	return n;
}

ResidueField operator-(const ResidueField &lhs, const ResidueField &rhs)
{
	if (!IsSameSystem(lhs, rhs))
		throw;

	if (lhs.mod == 0)
	{
		if (rhs.mod == 0)
			return ResidueField(lhs.num - rhs.num);
		else
			return ResidueField((lhs.num - rhs.num) % rhs.mod, rhs.mod, true);
	}
	else
		return ResidueField((lhs.num - rhs.num) % lhs.mod, lhs.mod, true);
}

ResidueField& ResidueField::operator-=(const ResidueField &subtrahend)
{
	if (!IsSameSystem(*this, subtrahend))
		throw;

	if (this->mod == 0)
	{
		if (subtrahend.mod == 0)
		{
			this->num -= subtrahend.num;
			return *this;
		}
		else
			return *this = ResidueField((this->num - subtrahend.num) % subtrahend.mod, subtrahend.mod, true);
	}
	else
	{
		this->num = (this->num - subtrahend.num) % this->mod;
		return *this;
	}
}

ResidueField& ResidueField::operator--()
{
	return *this -= 1;
}

ResidueField ResidueField::operator--(int)
{
	ResidueField n(*this);
	*this -= 1;
	return n;
}

ResidueField operator*(const ResidueField &lhs, const ResidueField &rhs)
{
	if (!IsSameSystem(lhs, rhs))
		throw;

	if (lhs.mod == 0)
	{
		if (rhs.mod == 0)
			return ResidueField(lhs.num * rhs.num);
		else
			return ResidueField((lhs.num * rhs.num) % rhs.mod, rhs.mod, true);
	}
	else
		return ResidueField((lhs.num * rhs.num) % lhs.mod, lhs.mod, true);
}

ResidueField& ResidueField::operator*=(const ResidueField &factor)
{
	if (!IsSameSystem(*this, factor))
		throw;

	if (this->mod == 0)
	{
		if (factor.mod == 0)
		{
			this->num *= factor.num;
			return *this;
		}
		else
			return *this = ResidueField((this->num * factor.num) % factor.mod, factor.mod, true);
	}
	else
	{
		this->num = (this->num * factor.num) % this->mod;
		return *this;
	}
}

ResidueField Square(const ResidueField &n)
{
	if (n.mod == 0)
		return Square(n.num);
	else
		return ResidueField(Square(n.num) % n.mod, n.mod, true);
}

ResidueField operator/(const ResidueField &lhs, const ResidueField &rhs)
{
	if (!IsSameSystem(lhs, rhs))
		throw;

	const ResidueField factor = Inverse(rhs);

	if (lhs.mod == 0)
	{
		if (factor.mod == 0)
			return ResidueField(lhs.num * factor.num);
		else
			return ResidueField((lhs.num * factor.num) % factor.mod, factor.mod, true);
	}
	else
		return ResidueField((lhs.num * factor.num) % lhs.mod, lhs.mod, true);
}

ResidueField& ResidueField::operator/=(const ResidueField &divisor)
{
	if (!IsSameSystem(*this, divisor))
		throw;

	const ResidueField factor = Inverse(divisor);

	if (this->mod == 0)
	{
		if (factor.mod == 0)
		{
			this->num *= factor.num;
			return *this;
		}
		else
			return *this = ResidueField((this->num * factor.num) % factor.mod, factor.mod, true);
	}
	else
	{
		this->num = (this->num * factor.num) % this->mod;
		return *this;
	}
}
